package com.zq.solution.algorithm.sort;

/**
 * @ClassName MergeSort
 * @Description 归并排序
 *归并算法的中心是归并两个已经有序的数组。归并两个有序数组A和B，就生成了第三个有序数组C。数组C包含数组A和B的所有数据项。
 * @Author ZQ
 * @Date 2020/11/5 10:44
 * @Version V1.0
 **/
public class MergeSort {
    /**
     * @Description: 合并有序数组  传入两个有序数组a和b，返回一个排好序的合并数组
     * 该方法有三个while循环，第一个while比较数组a和数组b的元素，并将较小的赋值到数组c；
     * 第二个while循环当a数组所有元素都已经赋值到c数组之后，而b数组还有元素，那么直接把b数组剩余的元素赋值到c数组；
     * 第三个while循环则是b数组所有元素都已经赋值到c数组了，而a数组还有剩余元素，那么直接把a数组剩余的元素全部赋值到c数组。
     * @Author: ZQ
     * @Date: 2020/11/5 11:00
     **/
    public static int[] merge(int[] a, int[] b){//非递归实现归并
        int[] c = new int[a.length + b.length];
        int ia = 0,ib = 0,ic = 0;
        while (ia < a.length && ib < b.length){
            if (a[ia] < b[ib]){
                c[ic++] = a[ia++];
            }else {
                c[ic++] = b[ib++];
            }
        }
        while (ia < a.length){
            c[ic++] = a[ia++];
        }
        while (ib < b.length){
            c[ic++] = b[ib++];
        }
        return c;
    }

    /**
     * @Description:
     * 归并排序的思想是把一个数组分成两半，排序每一半，然后用的marge()方法将数组的两半归并成为一个有序的数组。
     * 　　把每一半都分为四分之一，对每个四分之一进行排序，然后把它们归并成一个有序的一半。
     * 类似的，把每个四分之一分成八分之一，对每个八分之一进行排序，以此类推，反复的分割数组，
     * 直到得到的子数组是一个数据项，那这就是这个递归算法的边界值，也就是假定一个数据项的元素是有序的。
     * @Author: ZQ
     * @Date: 2020/11/5 10:58
     **/
    public static int[] mergeSort(int[] c,int start,int last){
        if(last > start){
            //也可以是(start+last)/2，这样写是为了防止数组长度很大造成两者相加超过int范围，导致溢出
            int mid = start + (last - start)/2;
            mergeSort(c,start,mid);//左边数组排序
            mergeSort(c,mid+1,last);//右边数组排序
            merge(c,start,mid,last);//合并左右数组
        }
        return c;
    }
    public static void merge(int[] c,int start,int mid,int last) {
        int[] temp = new int[last - start + 1];//定义临时数组
        int i = start;//定义左边数组的下标
        int j = mid + 1;//定义右边数组的下标
        int k = 0;
        while (i <= mid && j <= last) {
            if (c[i] < c[j])  temp[k++] = c[i++];
            else temp[k++] = c[j++];
        }
        //把左边剩余数组元素移入新数组中
        while (i <= mid) temp[k++] = c[i++];
        //把右边剩余数组元素移入到新数组中
        while (j <= last) temp[k++] = c[j++];

        //把新数组中的数覆盖到c数组中
        for (int k2 = 0; k2 < temp.length; k2++) c[k2 + start] = temp[k2];
    }


    public static void main(String[] args) {
//        int[] a = new int[]{1,3,5,7,9,11,13,15,17,19};
//        int[] b = new int[]{2,4,6,8,10,12,14,16,17,18,19};
//        for (Integer c : marge(a,b)){
//            System.out.print(c + ",");
//        }
        int[] a = new int[]{3,56,7,2,4,65,8,97,2,32,56,76,6,34,543,43,645,34,53,245};
        for (Integer c : mergeSort(a,0,a.length-1)){
            System.out.print(c + ",");
        }
    }
}
